import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s.length() < p.length()){
            return list;
        }
        //将目标串的字符都放在集合里
        Map<Character, Integer> mapS = new HashMap<>();
        Map<Character, Integer> mapP = new HashMap<>();
        int len = p.length();
        //将字符串p的字符都放在Hash表里面
        for(int i = 0; i < len; i++){
            char key = p.charAt(i);
            int val = mapP.getOrDefault(key, 0);
            mapP.put(key, val + 1);
        }
        int left = 0;
        int right = 0;
        while(right < s.length()){
            //进窗口
            char key = s.charAt(right);
            int val = mapS.getOrDefault(key, 0);
            mapS.put(key, val + 1);
            //出窗口
            if(right - left + 1 > len){
                char ch = s.charAt(left);
                int value = mapS.get(ch);
                if(value > 1){
                    mapS.put(ch, value - 1);
                }else{
                    mapS.remove(ch);
                }
                left++;
            }
            //更新结果
            if(right - left + 1 == len && isAnagram(mapS, mapP)){
                list.add(left);
            }
            right++;
        }
        return list;
    }
    private boolean isAnagram(Map<Character, Integer> mapS, Map<Character, Integer> mapP){
        for(Map.Entry<Character, Integer> entry : mapP.entrySet()){
            char key = entry.getKey();
            int val = entry.getValue();
            if(!mapS.containsKey(key) || mapS.get(key) != val){
                return false;
            }
        }
        return true;
    }

    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s.length() < p.length()){
            return list;
        }
        int[] arrS = new int[26];
        int[] arrP = new int[26];
        int len = p.length();
        for(int i = 0; i < len; i++){
            char ch = p.charAt(i);
            arrP[ch - 'a']++;
        }
        int left = 0;
        int right = 0;
        while(right < s.length()){
            //进窗口
            char chRight = s.charAt(right);
            arrS[chRight - 'a']++;
            //出窗口
            if(right - left + 1 > len){
                char chLeft = s.charAt(left);
                arrS[chLeft - 'a']--;
                left++;
            }
            //更新结果
            if(right - left + 1 == len && isAnagram1(arrS, arrP, p, len)){
                list.add(left);
            }
            right++;
        }
        return list;
    }
    private boolean isAnagram1(int[] arrS, int[] arrP, String p, int len){
        for(int i = 0; i < len; i++){
            char ch = p.charAt(i);
            if(arrS[ch - 'a'] != arrP[ch - 'a']){
                return false;
            }
        }
        return true;
    }

    public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s.length() < p.length()){
            return list;
        }
        int[] arrS = new int[26];
        int[] arrP = new int[26];
        int len = p.length();
        for(int i = 0; i < len; i++){
            char ch = p.charAt(i);
            arrP[ch - 'a']++;
        }
        int left = 0;
        int right = 0;
        int count = 0;
        while(right < s.length()){
            //进窗口
            char chRight = s.charAt(right);
            arrS[chRight - 'a']++;
            if(arrS[chRight - 'a'] <= arrP[chRight - 'a']){
                count++;
            }
            //出窗口
            if(right - left + 1 > len){
                char chLeft = s.charAt(left);
                if(arrS[chLeft - 'a'] <= arrP[chLeft - 'a']){
                    count--;
                }
                arrS[chLeft - 'a']--;
                left++;
            }
            //更新结果
            if(right - left + 1 == len && count == len){
                list.add(left);
            }
            right++;
        }
        return list;
    }
}
